home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2217 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.8 KB  |  70 lines
  1. Path: atglab.bls.com!Alun.Champion
  2. From: Alun.Champion@bridge.bst.bls.com (Alun Champion)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: 19 Jan 1996 22:01:41 GMT
  6. Organization: Computer People Inc.
  7. Message-ID: <ALUN.CHAMPION.96Jan19170141@g7240065.bridge.bst.bls.com>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>
  9.     <4dorr8$i58@cloner3.netcom.com>
  10. NNTP-Posting-Host: bstfirewall.bst.bls.com
  11. In-reply-to: a1s@ix.netcom.com's message of Fri, 19 Jan 1996 22:33:52 GMT
  12.  
  13. In article <4dorr8$i58@cloner3.netcom.com> a1s@ix.netcom.com (Andrew Snyder) writes:
  14.  
  15. : Bill Simpson <wsimpson@uwinnipeg.ca> wrote:
  16.  
  17. :> Is there a fast way to decide whether a number n is a power of 2?
  18.  
  19. :> The only thing I have thought of is that if n is power of 2
  20. :> log(n)/log(2) is an integer
  21. :> BUT this is going to be a SLOW computation.  Needs to be fast.
  22.  
  23. :> Since I am dealing with unsigned long ints, I guess I can just store all
  24. :> 31 powers of 2 in a table and compare to n.  Though I don't know a fast
  25. :> algorithm to compare a number to 31 numbers in an array.
  26.  
  27. :> Perhaps there is a tricky nonportable way to see if I have power-of-2 by 
  28. :> looking at bits?  (That is fine for this application)
  29.  
  30. : no tricks
  31.  
  32. : #define ISPOW2(x) (((x) & 1) ^ 1)
  33.  
  34. This doesn't answer his question - all this tells him is if x is even
  35. (i.e: x % 2 == 0)
  36.  
  37. You could try:
  38.  
  39. #include <limits.h>
  40.  
  41. int
  42. ispow2(unsigned long x)  
  43. {
  44.    int i;
  45.  
  46.    for (i = 1; i < sizeof(x) * CHAR_BIT; i++)
  47.        if ((x ^ (1 << i)) == 0)
  48.            return 1;
  49.  
  50.    return 0;
  51. }
  52.  
  53. Hope this helps
  54. Regards
  55.  
  56.     -A.
  57.                     
  58.                     
  59.                     
  60.                     
  61.                     
  62.                     
  63.                     
  64.                     
  65.                     
  66.                     
  67.  
  68. -- 
  69. | A.Champion                |
  70.